/**
 * 如何在 O(n) 的时间复杂度内查找一个无序数组中的第 K 大元素？
 * [6,3,8,2,1] 第4大元素 就是 6。 排序完得结果就是[1,2,3,6,8]，第4大元素就是 arr[4-1]
 * 这个问题就是求解出数组Arr，K-1 索引得值
 * 在使用快速排序时，选择最后一个值作为排序分割点 P，将小于P得值都放在左边，大于P得值放在右边，这时查看P值所在数组得索引i，如果i+1 = K，那么Arr[i]就是最终要解得值
 * 从前往后遍历数组（0-n-1）,使用一个变量i用于记录小于P得值得偏移量（i=0），变量j用于遍历数组元素(j=i)，如果Arr[j]>p,那么将arr[j] 与 arr[i] 交换值，同时i++,
 * i+1 = k,求解成功
 * i+1 != k,进入下一轮循环，如果i+1>k,那么进入左边数据，i+1<k,进入右边数组
 */

function kNum(arr: number[], k: number) {
  // arr 得长度必须大于等于k
  if (arr.length < k) {
    console.log('不存在第', k, '大元素');
    return;
  }

  let i = pToIndex(arr, 0, arr.length - 1);

  while (i + 1 != k) {
    if (i + 1 > k) {
      i = pToIndex(arr, 0, i - 1);
    } else {
      i = pToIndex(arr, i + 1, arr.length - 1);
    }
  }

  console.log('第', k, '大元素就是', arr[i]);
}

function pToIndex(arr: number[], start: number, end: number): number {
  let i = start;
  let p = arr[end];

  for (let j = i; j < end; j++) {
    if (arr[j] < p) {
      // let tmp = arr[i];
      // arr[i] = arr[j];
      // arr[j] = tmp;

      swap(arr, i, j);

      i += 1;
    }
  }

  swap(arr, i, end);

  // arr[end] = arr[i];
  // arr[i] = p;

  return i;
}

function swap(arr, i, j) {
  if (i === j) return;
  let tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

export {};

kNum([6, 9, 1, 4, 2, 3, 8], 5);
